//
// Created by mac on 1/24/22.
//

#include <iostream>
#include <vector>


using namespace std;

vector<vector<int>> generateMatrix(int n) {

    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    vector<vector<int>> res(n, vector<int>(n));

    int row = 0;
    int col = 0;
    vector<vector<bool>> seem(n, vector<bool>(n));
    int dir=0;

    for (int i = 1; i <= n*n; ++i) {
        res[row][col]=i;
        seem[row][col] = true;
        int nextRow = row+dirs[dir][0];
        int nextCol = col+dirs[dir][1];

        if(nextRow<0 || nextRow>=n||nextCol<0 || nextCol>=n||seem[nextRow][nextCol]){

            dir = (dir+1)%4;
        }
        row = row + dirs[dir][0];
        col = col + dirs[dir][1];
    }
    return res;
}
